package com.zpself.module.算法练习.计算;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author By ZengPeng
 * @Description 给定一个包含 n 个整数的数组 nums 和一个目标值 target，
 * 判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？
 * 找出所有满足条件且不重复的四元组。
 *
 *注意：答案中不可以包含重复的四元组。
 *
 * 示例：
 * 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
 * 满足要求的四元组集合为：
 * [
 *   [-1,  0, 0, 1],
 *   [-2, -1, 1, 2],
 *   [-2,  0, 0, 2]
 * ]
 *
 * @date in  2021/2/20 15:18
 * @Modified By
 */
public class 力扣_18_四数之和 {
    public static void main(String[] args) {
        List<List<Integer>> lists = fourSum(new int[]{1, 0, -1, 0, -2, 2}, 3);
        System.out.println(lists);
    }
    //题解：双循环  +  双指针
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        //排序
        Arrays.sort(nums);
        //双循环  +  双指针
        int a,b,len =  nums.length;
        List<List<Integer>> result = new ArrayList<>();
        for (a = 0; a <= len-4; a++) {
            if(a>0&&nums[a]==nums[a-1]) continue;      //确保nums[a] 改变了,  相同的值跳过
            for (b = a+1; b <= len-3; b++) {
                if(b>a+1&&nums[b]==nums[b-1]) continue;      //确保nums[b] 改变了
                int c=b+1,d=len-1;
                while (c<d){
                   int cur =  nums[a]+nums[b]+nums[c]+nums[d];

                   if(cur<target)
                       c++;
                   else if(cur>target)
                       d--;
                   else {
                       List<Integer> data = new ArrayList<>();
                       data.add(nums[a]); data.add(  nums[b]); data.add( nums[c]); data.add( nums[d]);
                       result.add(data);
                       while(c<d&&nums[c+1]==nums[c])      //确保nums[c] 改变了
                           c++;
                       while(c<d&&nums[d-1]==nums[d])      //确保nums[d] 改变了
                           d--;
                       c++;//这里因为刚好相等，所以左右都动一下
                       d--;
                   }
                }
            }
        }
        return  result;
    }
}
